1. Field of the Invention
The present invention relates to a high reliability system, an apparatus and method for generating connective relations to construct the high reliability system, and computer readable storage medium that stores a program to realize the method, and in particular, to such system, apparatus and method which can flexibly deal with constraints imposed on the system.
2. Description of the Prior Art
There is known a fault tolerance system of which reliability is assured. Such system is required to continue service even when a failure occurs in a part of the system. One of the prior arts of such system is disclosed in JPA 8-292933.
FIG. 24 is a block diagram showing a configuration of the prior art.
In this system, generation device 106 previously obtains connective relations among functional units (in case of parallel processors, processors and links each disposed between processors) in functional unit set (for example, parallel processors) 101 necessary to realize services, and stores connective relations in connective relation storage 5.
If detector 4 detects that failure occurs in a functional units contained in functional unit set 1, selector 3 selects connective relations that do not include failed units from the connective relations stored in connective relation storage 5. Based on this selection, alteration device 2 connects functional units in functional unit set 1 so as to resume providing the services.
Thus, in the prior art, whether the service can be resumed when a failure occurs in functional units depends on whether the connective relations not including the failed functional units is stored in connective relation storage 5. As a result, functional unit assignment device 107, which consists of constraint section 107a, naming section 107b, distribution section 107c and reserve section 107d, assigns functional units in such a way that a functional unit used in each connective relation does not duplicate as long as possible based on the reliability equation, and the connective relation is generated based on this assignment.
However, the functional unit assignment by such functional unit assignment device 107 causes the following disadvantages:
First, functional unit assignment device 107 assigns the functional unit used in each connective relation not in consideration of constraints such as a topology of the connective relation and operational timing. Therefore, in the prior art, when generation device 106 generates the connective relation, available functional units are extremely limited, and it is difficult to deal with the above constraints.
The assignment of the functional units to each connective relation has a number of options, and the reliability equation is an extremely complicated function in accordance with the duplicated manner of the functional unit assigned to each functional unit. Further, even if the constraints are taken into accounts, whether the connective relation capable of satisfying the constraint can be generated by using only the functional units assigned by functional unit assignment device 107 has not been determined until the connected relation is practically generated. Namely, in the prior art, even if the constraints are taken into accounts, it is necessary to solve an extremely complicated optimization problem, and thus there is a disadvantage in which a computational complexity required for generating the connective relation becomes large.
Further, in the prior art, the connective relation generated by generation device 106 is not altered later. Therefore, when the failed functional units contained in functional unit set 1 increase, situations where no available connective relation for alteration is stored in connective relation storage 105 often occur, and therefore, there is a disadvantage in which the high reliability of the system can not be obtained. Further, there is also a disadvantage in which the capacity of connective relation storage 5 is consumed uselessly.
In order to overcome the aforementioned disadvantages, the present invention has been made, and accordingly, has an object to provide a high reliability system capable of generating connective relations which satisfy constraints related to the connective relations among the functional units such as the topology of the connective relations and operational timings, an apparatus and method for generating the connective relations, and a computer readable storage medium that stores a program containing instructions for realizing the method with a computer.
Another object of the present invention is to provide a high reliability system capable of reducing the amount of computation for generating the connective relation, an apparatus and method for generating the connective relation capable of reducing the amount of computation, and a computer readable storage medium that stores a program containing instructions for realizing the method with a computer.
Further object of the present invention is to provide a high reliability system capable of maintaining the high reliability even if failed functional units increase, an apparatus and method for generating a connective relation capable of maintaining the high reliability even if failed functional units increase, and a computer readable storage medium that stores a program containing instructions for realizing the method with a computer.
According a first aspect of the present invention, there is provided a high reliability system, which comprises: a functional unit set having a plurality of functional units, each of the functional units being capable of be connected with any other functional unit; a reliability storing means for storing a reliability of each functional unit contained in the functional unit set; a cost assigning means for assigning to each functional unit a reliability cost as a cost in accordance with the reliability stored in the reliability storing means; a cost storing means for storing the cost of each functional unit; a constraint storing means for storing constraints on connections of the functional units contained in the functional unit set; a connective relation generating means for generating a plurality of sets of connective relations of the functional units in the functional unit set in accordance with the costs of the functional units stored in the cost storing means and the constraints stored in the constraint storing means; a connective relation storing means for storing the plurality of sets of the connective relations of the functional units generated by the connective relation generating means; a failed functional unit detecting means for detecting a failed functional unit among the functional units contained in the functional unit set; a selecting means for selecting, among the sets of connective relations of the plurality of functional units stored in the connective relation storing means, a set not containing the failed functional unit detected by the failed functional unit detecting means; and an altering means for connecting the functional units in the functional unit set in accordance with the selected set of the connective relations of the functional units.
According to a second aspect of the present invention, there is provided a high reliability system, which comprises: a functional unit set having a plurality of functional units, each of the functional units being capable of be connected with any other functional unit; a cost assigning means for assigning a random cost as a cost to each functional unit contained in the functional unit set; a cost storing means for storing the cost of each functional unit; a constraint storing means for storing constraints on connections of the functional unit contained in the functional unit set; a connective relation generating means for generating a plurality of sets of connective relations of the functional units in the functional unit set in accordance with the costs of the functional units stored in the cost storing means and the constraints stored in the constraint storing means; a connective relation storing means for storing the plurality of sets of the connective relations of the functional units generated by the connective relation generating means; a failed functional unit detecting means for detecting a failed functional unit among the functional units contained in the functional unit set; a selecting means for selecting, among the sets of connective relations of the plurality of functional units stored in the connective relation storing means, a set not containing the failed functional unit detected by the failed functional unit detecting means; and an altering means for connecting the functional units in the functional unit set in accordance with the selected set of the connective relations of the functional units.
According to a third aspect of the present invention, there is provided a high reliability system, which comprises: a functional unit set having a plurality of functional units, each of the functional units being capable of be connected with any other functional unit; a cost assigning means for assigning to each functional unit a cost corresponding to connective relations of the functional units as a cost, the connective relations being stored in a connective relation storing means; a cost storing means for storing the cost of each functional unit; a constraint storing means for storing constraints on connections of functional units contained in the functional unit set; a connective relation generating means for generating a plurality of sets of connective relations of the functional units in the functional unit set in accordance with the costs of the functional units stored in the cost storing means and the constraints stored in the constraint storing means; a connective relation storing means for storing the plurality of sets of the connective relations of the functional units generated by the connective relation generating means; a failed functional unit detecting means for detecting a failed functional unit among the functional units contained in the functional unit set; a selecting means for selecting, among the sets of the connective relations of the plurality of functional units stored in the connective relation storing means, a set not containing the failed functional unit detected by the failed functional unit detecting means; and an altering means for connecting the functional units in the functional unit set in accordance with the selected set of the connective relations of the functional units.
The high reliability system according to any aspect may further comprise: a detecting means for detecting a functional unit in a predetermined state in the functional unit set; and a state cost assigning means for adding a predetermined cost to the cost of the functional unit detected by the detecting means.
The high reliability system according to any aspect may further comprise: a detecting means for detecting a functional unit in a predetermined state in the functional unit set; and a constraint adding means for storing in the constraint storing means an additional constraint to disable the functional unit detected by the detecting means.
According to a fourth aspect of the present invention, there is provided an apparatus for generating connective relations of functional units contained in a functional unit set, the each functional unit being capable of be connected with any other functional unit, which apparatus comprises: a reliability storing means for storing a reliability of each functional unit contained in the functional unit set; a cost assigning means for assigning to each functional unit a reliability cost as a cost in accordance with the reliability stored in the reliability storing means; a cost storing means for storing the cost of each functional unit; a constraint storing means for storing constraints on connections of the functional units contained in the functional unit set; and a connective relation generating means for generating a plurality of sets of connective relations of the functional units in the functional unit set in accordance with the costs of the functional units stored in the cost storing means and the constraints stored in the constraint storing means.
According to a fifth aspect of the present invention, there is provided an apparatus for generating connective relations of functional units contained in a functional unit set, the each functional unit being capable of be connected with any other functional unit, which apparatus comprises: a cost assigning means for assigning a random cost as a cost to each functional unit contained in the functional unit set; a cost storing means for storing the cost of each functional unit; a constraint storing means for storing constraints on connections of the functional unit contained in the functional unit set; and a connective relation generating means for generating a plurality of sets of connective relations of the functional units in the functional unit set in accordance with the costs of the functional units stored in the cost storing means and the constraints stored in the constraint storing means.
According to a sixth aspect of the present invention there is provided an apparatus for generating connective relations of functional units contained in a functional unit set, the each functional unit being capable of be connected with any other functional unit, which apparatus comprises: a cost assigning means for assigning to each functional unit a cost corresponding to connective relations of the functional units as a cost, the connective relations being stored in a connective relation storing means existing externally; a cost storing means for storing the cost of each functional unit; a constraint storing means for storing constraints on connections of functional units contained in the functional unit set; and a connective relation generating means for generating a plurality of sets of connective relations of the functional units in the functional unit set in accordance with the costs of the functional units stored in the cost storing means and the constraints stored in the constraint storing means.
The apparatus for generating a connective relation according to any aspect may further comprise: a detecting means for detecting a functional unit in a predetermined state in the functional unit set; and a state cost assigning means for adding a predetermined cost to the cost of the functional unit detected by the detecting means.
The apparatus for generating a connective relation according to any aspect may further comprises: a detecting means for detecting a functional unit in a predetermined state in the functional unit set; and a constraint adding means for storing in the constraint storing means an additional constraint to disable the functional unit detected by the detecting means.
Other features and advantages of the invention will be apparent from the following description of the preferred embodiments thereof.